HJ77 火车进站

本节目标：理解“HJ77 火车进站”的核心思路，并能把它用于实际开发或面试表达。 中等 通过率：43.39% 时间限制：1秒 空间限制：32M 知识点==栈== 描述 给定一个正整数N代表火车数量，0<N<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号，火车站只有一个方向进出，同时停靠在火车站的列车中，只有后进站的出站了，先进站的才能出站。 要求输出所有火车出站的方案，以字典序排序输出。 数据范围：1≤n≤10 进阶：时间复杂度：O(n!) ，空间复杂度：O(n) 输入描述： 第一行输入一个正整数N（0 < N <= 10），第二行包括N个正整数，范围为1到10。 输出描述： 输出以字典序从小到大排序的火车出站序列号，每个编号以空格隔开，每个输出序列换行，具体见sample。 示例1 输入： 31 2 3 ==复制== 输出： 1 2 31 3 22 1 32 3 13 2 1 ==复制== 说明： 第一种方案：1进、1出、2进、2出、3进、3出第二种方案：1进、1出、2进、3进、3出、2出第三种方案：1进、2进、2出、1出、3进、3出第四种方案：1进、2进、2出、3进、3出、1出第五种方案：1进、2进、3进、3出、2出、1出请注意，[3,1,2]这个序列是不可能实现的。

这个问题可以通过递归方法来解决，核心思想是尝试所有可能的出站序列，并利用栈来模拟火车的进站和出站过程。对于每辆火车，都有两种选择：进站或者出站（如果栈非空）。

具体实现步骤如下：

1. 初始化两个栈，一个用于模拟火车进站（in_stack），一个用于存储当前的出站序列（out_stack）。
2. 递归地尝试每辆火车的进站和出站操作。

• 对于进站操作，将火车压入in_stack，然后递归处理下一辆火车。
• 对于出站操作，将in_stack的顶部元素弹出，加入到out_stack中，然后递归处理下一辆火车。

3. 当所有火车都已处理完毕，如果in_stack为空，则将当前的出站序列（out_stack）加入到结果集中。
4. 最后，将所有可能的出站序列按字典序排序，并输出。

代码示例：

定义一个深度优先搜索的递归函数，用于探索所有可能的火车出站顺序

def dfs(in_stack, out_stack, in_list, result):

如果没有火车需要进站，且站内也没有火车，记录当前的出站序列

if not in_list and not in_stack: result.append(' '.join(out_stack)) # 将当前出站序列添加到结果列表中 return

如果站内有火车，尝试将最后进站的火车出站

if in_stack: dfs(in_stack[:-1], out_stack + [in_stack[-1]], in_list, result) # 出站操作，递归调用dfs

如果还有火车未进站，尝试让下一辆火车进站

if in_list: dfs(in_stack + [in_list[0]], out_stack, in_list[1:], result) # 进站操作，递归调用dfs

主函数，处理输入和打印所有合法的出站顺序

def train_out(N, trains): result = [] # 初始化一个空列表，用于存储所有可能的出站顺序

调用dfs函数开始递归搜索，初始时站内无火车（in_stack为空），还未有火车出站（out_stack为空），待处理的火车序列为trains

dfs([], [], trains, result)

对找到的所有出站顺序进行排序，然后依次打印出来

for seq in sorted(result): print(seq)

读取输入数据

N = int(input().strip()) # 火车的数量 trains = input().strip().split() # 火车进站的序列

调用train_out函数处理输入并打印结果

train_out(N, trains)

这里dfs函数是递归的核心，它尝试所有可能的出站序列。in_stack代表当前站内的火车，out_stack代表已经出站的火车序列，in_list代表还未进站的火车。当in_list和in_stack都为空时，意味着所有火车都已经出站，此时的out_stack即为一种可能的出站序列。

需要注意的是，由于火车出站的顺序是有限制的（只有最后进站的火车可以出站），所以并不是所有的排列都是可能的，上述算法正是通过模拟进出站的过程来确保生成的出站序列是合法的。